package seqlist.doublelink;

public class Text{
    public class DoubleLinkedList {
        // 当前链表中有效的元素个数
        private int size;
        // 头节点
        private Node head;
        // 尾节点
        private Node tail;

        public void addFirst(int val) {
            Node node = new Node(null,val,head);
            if (head == null) {
                // 当前链表为空
                tail = node;
            }else {
                // 链表不为空
                head.prev = node;
            }
            // 无论链表是否为空，最后node节点都是最新的头节点
            head = node;
            size ++;
        }

        public void addLast(int val) {
            Node node = new Node(tail,val,null);
            if (tail == null) {
                head = node;
            }else {
                tail.next = node;
            }
            tail = node;
            size ++;
        }

        /**
         * 在链表的中间位置插入元素
         * @param index
         * @param val
         */
        public void addIndex(int index,int val) {
            if (index < 0 || index > size) {
                System.err.println("add index illegal!");
                return;
            }else if (index == 0) addFirst(val);
            else if (index == size) addLast(val);
            else {
                // 在中间位置插入，找到index的前驱节点
                // 找节点 -> 写成方法
                Node prev = node(index - 1);
                // 连接四根线
                Node newNode = new Node(prev,val,prev.next);
                prev.next.prev = newNode;
                prev.next = newNode;
                size ++;
            }
        }

        public int get(int index) {
            // index合法性
            if(rangeIndex(index)) {
                return node(index).val;
            }else {
                System.err.println("get index illegal!");
                return -1;
            }
        }

        public boolean contains(int val) {
            for (Node x = head;x != null;x = x.next) {
                if (x.val == val) {
                    return true;
                }
            }
            return false;
        }

        /**
         * 根据index修改元素值
         * @param index
         * @param newVal
         * @return 修改前的值
         */
        public int set(int index,int newVal) {
            if (rangeIndex(index)) {
                Node node = node(index);
                int oldVal = node.val;
                node.val = newVal;
                return oldVal;
            }else {
                System.err.println("set index illegal!");
                return -1;
            }
        }

        private boolean rangeIndex(int index) {
            if (index < 0 || index >= size) {
                return false;
            }
            return true;
        }

        @Override
        public String toString() {
            String ret = "";
            Node node = head;
            while (node != null) {
                ret += node.val + "->";
                node = node.next;
            }
            ret += "NULL";
            return ret;
        }

        public void removeFirst() {
            removeIndex(0);
        }

        public void removeLast() {
            removeIndex(size - 1);
        }

        public void removeIndex(int index) {
            if (rangeIndex(index)) {
                Node node = node(index);
                unlink(node);
            }else {
                System.err.println("remove index illegal!");
            }
        }

        public void removeValueOnce(int val) {
            // 找到待删除节点
            for (Node x = head;x != null;x = x.next) {
                if (x.val == val) {
                    unlink(x);
                    break;
                }
            }
        }

        public void removeValueAll(int val) {
            for (Node x = head;x != null;) {
                if (x.val == val) {
                    // x是待删除节点
                    // next是下一个要判断的节点
                    Node next = x.next;
                    // 删除之后，x.next = x.prev = null
                    unlink(x);
                    x = next;
                }else {
                    // 继续向后走
                    x = x.next;
                }
            }
        }

        /**
         * 在双向链表中删除指定的node节点
         * @param node
         */
        private void unlink(Node node) {
            // 分治思想
            Node prev = node.prev;
            Node next = node.next;
            // 先处理前驱节点
            if (prev == null) {
                // 此时是个头节点
                head = next;
            }else {
                // 有前驱
                prev.next = next;
                node.prev = null;
            }
            // 此时接着处理后半边的情况
            if (next == null) {
                // 此时node是个尾节点
                tail = prev;
            }else {
                next.prev = prev;
                node.next = null;
            }
            size --;
        }

        /**
         * 找到index索引对应的节点
         * @param index
         * @return index对应的节点Node
         */
        private Node node(int index) {
            Node ret = null;
            // index < size / 2(从头找)
            if (index < (size >> 1)) {
                ret = head;
                for (int i = 0; i < index; i++) {
                    ret = ret.next;
                }
            }else {
                // 此时从后向前遍历
                ret = tail;
                for (int i = size - 1;i > index;i--) {
                    ret = ret.prev;
                }
            }
            return ret;
        }
    }

    /**
     * 双链表的节点类
     */
    class Node {
        // 指向前驱节点
        Node prev;
        // 保存具体值
        int val;
        // 指向后继节点
        Node next;

        public Node(int val) {
            this.val = val;
        }

        public Node(Node prev, int val, Node next) {
            this.prev = prev;
            this.val = val;
            this.next = next;
        }
    }
}
